package leetcode_day._2021._202105._1120;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/5/19 22:24
 * 找出第 K 大的异或坐标值
 * 算法：位运算  前缀和
 * 求前缀和
 * pre[i][j] = pre[i][j - 1] ^ prs[i - 1][j] ^ pre[i - 1][j - 1] ^ matrix[i - 1][j - 1]
 */
public class _19_1738 {
    public static void main(String[] args) {
        // [[10,9,5],[2,0,4],[1,0,9],[3,4,8]]
        //10
        int[][] matrix = {{10, 9, 5}, {2, 0, 4}, {1, 0, 9}, {3, 4, 8}};
//        int[][] matrix = {{5, 2}, {1, 6}};
        System.out.println(new _19_1738().kthLargestValue(matrix, 10));
    }

    public int kthLargestValue(int[][] matrix, int k) {
        int m = matrix.length, n = matrix[0].length;
        int[][] pre = new int[m + 1][n + 1];
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                pre[i][j] = pre[i - 1][j - 1] ^ pre[i][j - 1] ^ pre[i - 1][j] ^ matrix[i - 1][j - 1];
                list.add(pre[i][j]);
            }
        }
        Collections.sort(list);
        return list.get(m * n - k);
    }
}
